<!DOCTYPE html>
<html lang="en">
    <head>
    <title>Greedy Algo: Interval Scheduling - Tinusgraglin</title>
    
    
    <meta http-equiv="content-type" content="text/html; charset=utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1"><meta name="description" content="A Slice Greedy Algo: Interval Scheduling My attack on the interval scheduling problem."/><meta name="keywords" content="algo, greedy-algo" />
    <meta property="og:title" content="A Slice of Tgl -&nbsp;Greedy Algo: Interval Scheduling" />
    <meta property="og:type" content="website"/><meta property="og:url" content="&#x2F;blog&#x2F;interval-scheduling&#x2F;"/><meta property="og:description" content="My attack on the interval scheduling problem."/>
    <link rel="preload" href="/blog/assets/fonts/FiraCode-Regular.woff2" as="font" type="font/woff2" crossorigin="anonymous">
    <link rel="preload" href="/blog/assets/fonts/FiraCode-Bold.woff2" as="font" type="font/woff2" crossorigin="anonymous">

    <link rel="stylesheet" href="/blog/style.css?h=97e262212a0704163528">
    <link rel="stylesheet" href=" /blog/color/orange.css?h=a5a5d7faf9d4bc3e0b18">
    

  

  <link rel="stylesheet" href="/blog/assets/katex/katex.min.css">

  <script defer type="text/javascript" src="/blog/assets/katex/katex.min.js"></script>
  <script defer type="text/javascript" src="/blog/assets/katex/mathtex-script-type.min.js"></script>

  <script defer src="/blog/assets/katex/auto-render.min.js"
    onload="renderMathInElement(document.body, {
				delimiters: [
					{left: '$$', right: '$$', display: true},
					{left: '$', right: '$', display: false},
					{left: '\\(', right: '\\)', display: false},
					{left: '\\[', right: '\\]', display: true}
				]
			});"></script>


  </head>
    <body>
        <div class="container center">
<header class="header">
    <div class="header__inner">
        <div class="header__logo">
            <a href="&#x2F;blog">
    <div class="logo">
        LIN
    </div>
</a>
        </div>
        <div class="menu-trigger">menu</div>
    </div>
    
    <nav class="menu">
        <ul class="menu__inner menu__inner--desktop">
            
            
                    <li>
                        <a href="
    
        /blog/about
    
">about</a>
                    </li>
                
            </ul>

        <ul class="menu__inner menu__inner--mobile">
            
        <li>
            <a href="
    
        /blog/about
    
">about</a>
        </li>
        </ul>
    </nav>

    </header>
<div class="content"><article class="post">
        <header>
            <h1 class="post-title">
                <a href="&#x2F;blog&#x2F;interval-scheduling&#x2F;">Greedy Algo: Interval Scheduling</a>
            </h1>
            
    <div class="post-meta">
        <span class="post-date">2022.10.03
                </span>

        <span class="post-author"></span>

        

    
    :: {<a href="/blog/categories/algo/">algo</a>} 

            
    ::
    #<a href="/blog/tags/greedy-algo/">greedy-algo</a>
        
    
            
        
    </div>

            
    
</header><p>Problem: Given a set of intervals of the form $(l,r)$, pick as many non-overlapping intervals as possible from the set.</p>
<p>Greedy approach: always pick the interval that 1. does not overlap with the region covered by previously picked intervals 2. has the smallest end value until all the un-picked intervals overlap with the region covered by previously picked intervals.</p>
<p>Let $G=g_1,g_2,g_3,\cdots,g_k$ be the sequence generated by the greedy algorithm. Now <strong>assume that $G$ is not the optimal answer</strong>, that is, there exist some optimal answer that includes $m$ intervals such that $m&gt;k$, let $O$ be <strong>any</strong> such answer, and we <strong>sort</strong> its $m$ intervals by their start value (or by their end value, since they are mutually exclusive) and express $O$ as this sorted sequence:</p>
<p>$$O=o_1,o_2,o_3,\cdots,o_k,\cdots,o_m$$</p>
<p>Now we compare $O$ and $G$, and claim that <strong>$O$ can not agree with $G$ on the first $k$ intervals</strong> and we prove this claim by contradiction: if $O$ and $G$ do agree on the first $k$ intervals, then since $G$ stops at the $k$-th interval, that means no interval that do not overlap with the first $k$ intervals can be found, which contradict the fact that $O$ still continues after the first $k$ intervals.</p>
<p>Thus $O$ and $G$ can only agree on the first $l$ intervals where $0\le l&lt;k$. Then we can construct a new sequence $S$ from $O$ by replacing $o_{l+1}$ with $g_{l+1}$:</p>
<p>$S=o_1,\cdots,o_{l-1},o_l,g_{l+1},o_{l+2},\cdots,o_m$</p>
<p>and since $O$ and $G$ agree on the first $l$ intervals, this can also be written as:</p>
<p>$$S=g_1,\cdots,g_{l-1},g_l,g_{l+1},o_{l+2},\cdots,o_m$$</p>
<p>And we claim that <strong>no two intervals in $S$ overlap.</strong> To see this, note that we only replaced $o_{l+1}$ with $g_{l+1}$, so if there does exist any overlap introduced by this alteration, it can only involve $g_{l+1}$. So first of all, we see that $g_{l+1}$ can not overlap with $g_1,\cdots,g_l$, the first $l$ intervals of $S$, because $g_1,\cdots,g_l,g_{l+1}$ are picked sequentially by the algorithm, which guaranteed that they do not overlap. And second, since $g_{l+1}$ is picked because it has the smallest end value of all intervals that do not overlap with $g_1,\cdots,g_{l}$ ($o_1,\cdots,o_l$) (thus includes $o_{l+1},o_{l+1},\cdots,o_m$), the end value of $g_{l+1}$ is smaller than any of $o_{l+1},o_{l+2},\cdots,o_m$. Particularly, since the end of $g_{l+1}$ is smaller than that of $o_{l+1}$, and $o_{l+2},\cdots,o_m$ all come after $o_{l+1}$, $g_{l+1}$ can not possibly overlap with $o_{l+2},\cdots,o_m$.</p>
<p>Since no two intervals in $S$ overlap, and it also includes $m$ intervals, we claim that $S$ is also an optimal answer of the problem, just like $O$. But now, $S$ agrees with $G$ on the first $l+1$ intervals. We can thus continue doing this until we have a sequence $S'$ that 1. is an optimal answer to the problem 2. agrees with $G$ on the first $k$ intervals. But we have proved that no optimal answer $O$ can agree with $G$ on the first $k$ interval!</p>
<p>This contradiction leads us to conclude that our assumption that G is not the optimal answer of the problem is <strong>not</strong> true.</p>


        
    

        
        
    </article></div>
    <div class="pagination">
        <div class="pagination__buttons">
            </div>
    </div>
<footer class="footer">
                    <div class="footer__inner"><div class="copyright">
            <span>© 2024 Tinusgraglin <span/>
            <span>:: Powered by <a href="https://www.getzola.org/">Zola</a>(<a href="https://www.rust-lang.org/">Rust</a>) and <a href="https://bun.sh">Bun</a>(<a href="https://ziglang.org">Zig</a>)</span>
        </div>
    <script type="text/javascript" src="/blog/assets/js/main.js"></script>
</div>
                    

                </footer></div>
    </body>
</html>
